package monotonestack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Classname : LargestRectangleInHistogram
 * @Description : 84. 柱状图中最大的矩形
 * https://leetcode.cn/problems/largest-rectangle-in-histogram/
 * 本题单调栈用法：获取一维数组中左侧第一个小于当前位置取值的下标
 * @Author : cty
 * @Date 2023/3/26 23:57
 */


public class LargestRectangleInHistogram {
    public int largestRectangleArea(int[] heights) {
        int ans = 0, n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int[][] bounds = new int[2][n];
        Arrays.fill(bounds[0], -1);
        Arrays.fill(bounds[1], n);

        // 遍历柱状图，找到每根柱子的左边界位置bounds[i][0]和右边界位置bounds[i][1]
        // 边界处的柱子高度小于当前柱子的高度
        for (int i = 0; i < n; i++) {
            // 出栈时当前位置是出栈位置的右边界（即使出现相等柱子，最右边柱子的右边界一定是正确的且最大的）
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                bounds[1][stack.pop()] = i;
            }
            // 入栈时栈顶位置是当前位置的左边界
            if (!stack.isEmpty()) {
                bounds[0][i] = stack.peek();
            }
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (bounds[1][i] - bounds[0][i] - 1));
        }
        return ans;
    }
}
